| |
| description |
10 pages
|
|
We present a family of new top-down parsing algorithms for arbitrary
context-free grammars based on the notion of a "tree of
possible left-derivations". When coded in a special way, this
tree can be compressed to a graph. While the time complexity on
uniform RAMs is O(n^3) in worst case, we need O(n^2) space. We show
that the asymptotic time complexities are equal to Earley's
algorithms, and give some arguments to show our algorithm will be
better in almost all cases.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Technical Report
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-1991-07/TR-1991-07.pdf
|
| contributor |
Betriebssoftware (IFI)
|
| format |
application/pdf
|
| subject |
Programming Languages Processors (CR D.3.4)
|
| Grammars and Other Rewriting Systems (CR F.4.2)
|
| relation |
Technical Report No. 1991/07
|